Imagine an agent moving along a circular path in the plane with some stationary landmarks, whose number and exact locations are unknown to the agent. Suppose that each landmark transmits an omnidirectional signal with a finite range, which we can model as a function that equals 1 inside a circular disk centered at the landmark and 0 outside. The boundaries of these disks, whose radii are in general different, may intersect the agent's path at one or two points or not at all. As the agent moves along its path, it can perceive these signals and so it knows, at each point, the number of landmarks that are within range. It cannot, however, identify different landmarks by their signals, and neither can it discern anything about each signal's strength other than its presence or absence. The agent's knowledge of its position on the circle may also not be precise, and the signal transmissions or measurements may occur with some sampling frequency rather than continuously in time. For these reasons, all that the agent can reliably reconstruct is a sequence of nonnegative integers corresponding to local landmark counts around the circle, and it may not be sure of the precise count at the exact points where this count changes. In this scenario, we want to pose the following questions: Can the agent figure out the total number of landmarks (excluding, of course, those whose signals do not reach any points on the circle)?

Superresolution theory and techniques seek to recover signals from samples in the presence of blur and noise. Discrete image registration can be an approach to fuse information from different sets of samples of the same signal. Quantization errors in the spatial domain are inherent to digital images. We consider superresolution and discrete image registration for one-dimensional spatially-limited piecewise constant functions which are subject to blur which is Gaussian or a mixture of Gaussians as well as to round-off errors. We describe a signal-dependent measurement matrix which captures both types of effects. For this setting we show that the difficulties in determining the discontinuity points from two sets of samples even in the absence of other types of noise. If the samples are also subject to statistical noise, then it is necessary to align and segment the data sequences to make the most effective inferences about the amplitudes and discontinuity points. Under some conditions on the blur, the noise, and the distance between discontinuity points, we prove that we can correctly align and determine the first samples following each discontinuity point in two data sequences with an approach based on dynamic programming.

Sampling and quantization are standard practices in signal and image processing, but a theoretical understanding of their impact is incomplete. We consider discrete image registration when the underlying function is a one-dimensional spatially-limited piecewise constant function. For ideal noiseless sampling the number of samples from each region of the support of the function generally depends on the placement of the sampling grid. Therefore, if the samples of the function are noisy, then image registration requires alignment and segmentation of the data sequences. One popular strategy for aligning images is selecting the maximum from cross-correlation template matching. To motivate more robust and accurate approaches which also address segmentation, we provide an example of a one-dimensional spatially-limited piecewise constant function for which the cross-correlation technique can perform poorly on noisy samples. While earlier approaches to improve the method involve normalization, our example suggests a novel strategy in our setting. Difference sequences, thresholding, and dynamic programming are well-known techniques in image processing. We prove that they are tools to correctly align and segment noisy data sequences under some conditions on the noise. We also address some of the potential difficulties that could arise in a more general case.

We consider a nonlinear state-space model with the state transition and observation functions expressed as basis function expansions. The coefficients in the basis function expansions are learned from data. Using a connection to Gaussian processes we also develop priors on the coefficients, for tuning the model flexibility and to prevent overfitting to data, akin to a Gaussian process state-space model. The priors can alternatively be seen as a regularization, and helps the model in generalizing the data without sacrificing the richness offered by the basis function expansion. To learn the coefficients and other unknown parameters efficiently, we tailor an algorithm using state-of-the-art sequential Monte Carlo methods, which comes with theoretical guarantees on the learning. Our approach indicates promising results when evaluated on a classical benchmark as well as real data.

We consider the problem of minimizing the regret in stochastic multi-armed bandit, when the measure of goodness of an arm is not the mean return, but some general function of the mean and the variance. We characterize the conditions under which learning is possible and present examples for which no natural algorithm can achieve sublinear regret.